package com.leetcode.solution.s9x;

public class NumDecodings91 {
    public static void main(String[] args) {
        String s = "226";
        int rst = new NumDecodings91().numDecodings(s);
        System.out.println(rst);
    }

    public int numDecodings(String s) {
        char[] chs = s.toCharArray();
        // 由于是按照长度来设计长度缓存的，所以数组总长度为length + 1
        int[] decodes = new int[chs.length + 1];

        // 空字符（length=0）串可以有 1 种解码方法，解码出一个空字符串
        decodes[0] = 1;
        for (int len = 1; len <= chs.length; len++) {
            // 动态规划的方法求解，当前位=len-1
            // 一个字符的情况，确保第len-1位 ！= 0
            if (chs[len - 1] != '0') {
                decodes[len] += decodes[len - 1];
            }

            // 当前选择2位的情况 + 前n-2位解法
            if ( len > 1 && chs[len - 2] != '0' && (chs[len - 2] - '0') * 10 + (chs[len - 1] - '0') <= 26) {
                decodes[len] += decodes[len - 2];
            }
        }

        return decodes[decodes.length - 1];
    }
}
